package main

import (
	"bytes"
	"fmt"
)

/*
如果查看集合中是否有8这个值，我们用uint64数据类型表示：0000...0000(64个0)。如果低位第八位是1，
则表示集合含有这个元素8。但是uint64数据类型的数据空间长度只有64位，只能表示非负整数，且数值范围1~64，
大于64的元素值无法表示，这就需要引入slice动态数据表示

这样说不知道读者是否理解，如果理解，下面这个DEMO就容易明白。当然这很浪费空间，
因为如果是稀疏数据的话，严重浪费空间。先不管这些，这要考虑到压缩，或者编码问题。
*/

type IntSet struct {
	words []uint64
}

func (s *IntSet) Has(x int) bool {
	word, bit := x/64, uint(x%64)
	return word < len(s.words) && s.words[word]&(1<<bit) != 0
}

func (s *IntSet)Add(x int){
	word, bit := x/64, uint(x%64)
	for len(s.words)<=word{
		s.words = append(s.words, 0)
	}
	s.words[word] |= 1 << bit
}

// 经典的数组合并逻辑
func (s *IntSet) Union(t *IntSet) {
	for i,_ := range t.words{
		if i < len(s.words){
			s.words[i] |= t.words[i]
		}else{
			s.words = append(s.words, t.words[i])
		}
	}
}

func (s *IntSet)String() string{
	var buf bytes.Buffer
	buf.WriteByte('{')
	for i,word := range s.words{
		if word == 0{
			continue
		}
		var j uint = 0
		for ; j<64; j++{
			if (word & (1<<j)) != 0 {
				if buf.Len() > len("{"){ //说明已经添加了元素，要加个空格和之前的元素分开
					buf.WriteByte(' ')
				}
				// bytes.Buffer实现 Write方法的是 b *Buffer, 而不是 b Buffer 所以只能用指针 &buf
				fmt.Fprint(&buf, "%d", 64 * i + int(j))
			}
		}
	}
	buf.WriteByte('}')
	return buf.String()
}

var s string

func runA() {
	taste(s)
}
func taste(i *string) {

}